﻿
using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0002_Intersect
    {
        // 两个数组的交集 II

        // 给定两个数组，编写一个函数来计算它们的交集。

        // 说明：
        //  输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
        //  我们可以不考虑输出结果的顺序。

        // 进阶：
        //  如果给定的数组已经排好序呢？你将如何优化你的算法？
        //  如果 nums1 的大小比 nums2 小很多，哪种方法更优？
        //  如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？


        public void Test()
        {
            var nums1 = new int[] { 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5 };
            var nums2 = new int[] { 1, 4, 6, 7, 12, 3, 4, 5, 7 };
            var result = Intersect2(nums1, nums2);

            foreach (var item in result)
            {
                Console.Write(item + ",");
            }
            Console.ReadLine();
        }

        // 排序+指针
        public int[] Intersect(int[] nums1, int[] nums2)
        {
            Array.Sort(nums1);
            Array.Sort(nums2);
            var result = new List<int>();
            int fPointer = 0, sPointer = 0;
            while (fPointer < nums1.Length && sPointer < nums2.Length)
            {
                if (nums1[fPointer] == nums2[sPointer])
                {
                    result.Add(nums1[fPointer]);
                    fPointer++;
                    sPointer++;
                }
                else if (nums1[fPointer] < nums2[sPointer])
                    fPointer++;
                else
                    sPointer++;
            }
            return result.ToArray();
        }

        // hash

        public int[] Intersect2(int[] nums1, int[] nums2)
        {
            var numsDic = new Dictionary<int, int>();
            if (nums1.Length < nums2.Length)
                for (int i = 0; i < nums1.Length; i++)
                {
                    if (numsDic.ContainsKey(nums1[i]))
                        numsDic[nums1[i]]++;
                    else
                        numsDic.Add(nums1[i], 1);
                }
            else
                for (int i = 0; i < nums2.Length; i++)
                {
                    if (numsDic.ContainsKey(nums2[i]))
                        numsDic[nums2[i]]++;
                    else
                        numsDic.Add(nums2[i], 1);
                }
            var result = new List<int>();
            if (nums1.Length < nums2.Length)
                for (int i = 0; i < nums2.Length; i++)
                {
                    if (numsDic.TryGetValue(nums2[i], out int value))
                    {
                        result.Add(nums2[i]);
                        if (value == 1)
                            numsDic.Remove(nums2[i]);
                        else
                            numsDic[nums2[i]]--;
                    }
                }
            else
                for (int i = 0; i < nums1.Length; i++)
                {
                    if (numsDic.TryGetValue(nums1[i], out int value))
                    {
                        result.Add(nums1[i]);
                        if (value == 1)
                            numsDic.Remove(nums1[i]);
                        else
                            numsDic[nums1[i]]--;
                    }
                }
            return result.ToArray();
        }
    }
}
